package q2305_distributeCookies;


import java.util.Arrays;

/*
此题应结合1723 473 698 三题 本质都是向多个桶中尽可能均量的放入物品
都是用回溯的方式来解决
 */
public class Solution {
    int[] cookies;
    int n;
    int k;
    int ans;
    public int distributeCookies(int[] cookies, int k) {
        this.cookies = cookies;
        this.k = k;
        this.n = cookies.length;
        ans = Integer.MAX_VALUE;
        // 排序非常重要 先发饼干较多的包，这样让回溯过程更快
        Arrays.sort(cookies);
        backtrack(new int[k], n - 1);

        return ans;
    }

    private void backtrack(int[] bucket, int start) {
        if (start < 0) {
            int cur = 0;
            for (int i : bucket) cur = Math.max(cur, i);

            ans = Math.min(cur, ans);
            return;
        }

        // 剪枝1
        // 题中设定饼干数量大于小孩个数 那么当饼干数量不够小孩分时 代表有多的饼干集中到了至少一个小孩上 那么此时求出的ans必然不是最低解
        int zeroBucket = 0;
        for (int i : bucket) {
            if (i == 0) ++zeroBucket;
        }
        if (zeroBucket > start + 1) return;
        // 剪枝2
        // 如果有一个bucket已经聚集了大于此时ans数量的饼干 显然也不是最优解
        for (int i = 0; i < k; i++){
            if (bucket[i] > ans) return;
        }

        for (int i = 0; i < bucket.length; ++i) {
            bucket[i] += cookies[start];
            backtrack(bucket, start - 1);
            bucket[i] -= cookies[start];
        }
    }
}
